home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 051-075 / disk_075 / fd / fd.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  20KB  |  565 lines
  1. /************************************************************
  2.   fd.c        - fast directory
  3.  
  4.   By Stephen Vermeulen
  5.  
  6.   3635 Utah Dr., N.W.,
  7.   Calgary, Alberta, CANADA.
  8.   (403) 282-7990
  9.  
  10.   This code adds to Leo Schwab's attempt at making a faster
  11.   dir command with "eless".
  12.  
  13.   What I have done is to use Leo's program to track the way
  14.   the directory blocks are scattered about the disk and to
  15.   realize that with his near-optimum approach there will
  16.   still be several read attempts on each track.  This is a
  17.   result of the hash chains.  For example if track A contains
  18.   8 directory blocks, then at the first level of the hash
  19.   chain structure only 3 of these blocks may be read.  Then
  20.   at another level or two in the hash chain the other 5
  21.   directory blocks are accessed.  This results in many extra
  22.   seeks and reads of the same track.
  23.  
  24.   So what I have done is to process the ENTIRE track (both
  25.   surfaces or 22 blocks) once it is addressed by a hash
  26.   chain.  When I process a track I save the needed information
  27.   in an instance of the "disk_block" structure and chain it
  28.   onto the appropriate track (actually cylinder) pointer.
  29.   Only blocks which represent UserDirectories or FileHeaders
  30.   are recorded, the others are ignored.  Since there could be
  31.   blocks from several directories intermixed on the same track
  32.   we save only the information about blocks which belong to
  33.   our directory.  We do this by checking that DOS's parent
  34.   directory back pointer points to the initial block of our
  35.   directory.
  36.  
  37.   Then when I detect a read of a sector on a track that has
  38.   already been processed I just look it up in this structure
  39.   rather than having to seek back to the track.  This results
  40.   in about a 30-50% improvement in speed (over eless) on large directories.
  41.   For example, a directory with 223 files in it takes:
  42.  
  43.          fd      22 seconds
  44.          eless   30 seconds
  45.          dir     81 seconds.
  46.  
  47.   This routine may actually be slower on small directories.
  48.  
  49.   Additional improvements in speed may be obtained by going for the
  50.   track disk's buffer directly when determining which of the blocks
  51.   actually need to be recorded for possible future use.  Also, it
  52.   should be possible to pre-read the next track while processing the
  53.   current track.
  54.  
  55.   Thanks Leo, sorry I messed with your TABBING, I hate tabs...
  56.   (It still compiles under MANX 3.4A no sweat.)
  57.  
  58.   Will someone add the additional generality so this program can
  59.   print the directories of NON-BLOCK devices too?
  60.  
  61.   KNOWN BUG:
  62.  
  63.      It seems if you try to read blocks on a track that have never
  64.      been used before you get a System Requester with the message:
  65.  
  66.          Volume
  67.          test
  68.          has a read/write error.
  69.  
  70.      Unfortnately, one does not seem to be able to turn off these
  71.      error messages (even using the Process structure's WindowPtr
  72.      field).  This is not fatal, but is dammed inconvenient; you
  73.      just have to keep clicking cancel to jump those blocks.
  74.      To see this happen, format a disk then copy one file onto it.
  75.      Then do a "fd df0:" of the disk.  You will probably get a few
  76.      of these requesters.  Some of the Fish Disk also have a few
  77.      blocks that have never been used either.  Note: DiskEd gives
  78.      two different types upon reading one of these blocks:
  79.      Corrupt or Deleted Corrupt when the info (i) command is used
  80.      to examine the block.
  81.  
  82. ******************************************************************/
  83.  
  84.  
  85. /* :ts=8 bk=0
  86.  *
  87.  * eless.c:     An attempt at a reasonable-speed 'ls' program by fiddling
  88.  *              with the DOS.
  89.  *
  90.  *              Compiles under Manx 3.20 and patched 3.40.
  91.  *              cc eless.c
  92.  *              ln eless.c -lc -o eless
  93.  *
  94.  * Leo L. Schwab                8704.26         (415)-456-6565
  95.  */
  96.  
  97. #include <exec/types.h>
  98. #include <exec/memory.h>
  99. #include <libraries/dosextens.h>
  100. #include <stdio.h>
  101.  
  102. #define BLOCKSIZE       128
  103. #define STARTTAB        6
  104. #define ENDTAB          (BLOCKSIZE-51)
  105. #define TABSIZ          (BLOCKSIZE-56)
  106. #define FILENAME        (BLOCKSIZE-20)
  107. #define HASHCHAIN       (BLOCKSIZE-4)
  108. #define SECONDARY       (BLOCKSIZE-1)
  109. #define PARENT          (BLOCKSIZE-3)
  110. #define ST_DIR          2
  111. #define ST_FILE         -3
  112. #define ST_SHORT        2
  113.  
  114. struct disk_block
  115. {
  116.   struct disk_block *db;
  117.   long type;
  118.   char name[64];
  119.   long chain;
  120.   long number;
  121. };
  122.  
  123. /***************************************************
  124.   The following array holds the base pointers to the
  125.   blocks that have been read from each track.  At the
  126.   start this will be set to all NULLs, then as each
  127.   track is read in the pointer to the list of disk
  128.   blocks that contain relevant information for that
  129.   track is added into the array.  In this way we
  130.   seek to, and read each track only once.  Hence, if
  131.   we want a single block on a new track we scan all
  132.   the blocks on that track, and record any of the blocks
  133.   that are UserDirectory or FileHeader type blocks
  134.   in that track in this list.
  135. *****************************************************/
  136.  
  137. struct disk_block *tracks[80];
  138.  
  139. /*
  140.  * Note:  I usually declare Amiga functions this way to disable the compiler's
  141.  * type checking.  This allows me to assign values to variables without
  142.  * explicitly casting them to the appropriate type.  In reality, these
  143.  * functions return things entirely different from the way I've declared
  144.  * them.  For example, CreatePort() should really be declared as:
  145.  *
  146.  * struct MsgPort *CreatePort();
  147.  *
  148.  * Caveat Programmer.
  149.  */
  150. extern void     *AllocMem(), *CreatePort(), *RemTail(), *FindTask();
  151. extern long     Lock(), Examine();
  152.  
  153. long            dopacket();
  154. int             longcmp(), namecmp();
  155.  
  156.  
  157. struct StandardPacket   *packet;
  158. struct FileInfoBlock    *fib;
  159. struct FileLock         *lock;
  160. struct InfoData         *id;
  161. struct MsgPort          *dosreply;
  162. BPTR                    lok;
  163. long                    *buf, hashtab[TABSIZ];
  164.  
  165.  
  166. struct disk_block *free_disk_block(db)
  167. struct disk_block *db;
  168. {
  169.   struct disk_block *next_db;
  170.  
  171.   if (!db) return(NULL);
  172.   next_db = db->db;
  173.   FreeMem(db, (long) sizeof(struct disk_block));
  174.   return(next_db);
  175. }
  176.  
  177. main (ac, av)
  178. char **av;
  179. {
  180.         int flag;
  181.         struct Process *my_proc;
  182.         APTR w_save;
  183.  
  184.         openstuff ();
  185.  
  186.         my_proc = (struct Process *) FindTask(0L);
  187.  
  188.         /****************************************
  189.           The following is used to suppress error
  190.           messages that can occur when we attempt
  191.           to read sectors that have never been
  192.           used on the disk.
  193.         *****************************************/
  194.  
  195.         w_save = my_proc->pr_WindowPtr;
  196.         my_proc->pr_WindowPtr = (APTR) (-1);
  197.         if (ac < 2)             /*  No arguments; do current directory  */
  198.                 printdir (my_proc -> pr_CurrentDir);
  199.  
  200.         else {                  /*  Arguments; treat as directories  */
  201.                 flag = (ac > 2);
  202.                 while (++av, --ac) {
  203.                         if (!(lok = Lock (*av, ACCESS_READ))) {
  204.                                 printf ("%s: Not found.\n", *av);
  205.                                 if (ac > 1)
  206.                                         putchar ('\n');
  207.                                 continue;
  208.                         }
  209.  
  210.                         if (!Examine (lok, fib))
  211.                                 die ("Examine failed.");
  212.                         if (fib -> fib_DirEntryType < 0) {
  213.                                 printf ("%s: Not a directory.\n", *av);
  214.                                 if (ac > 1)
  215.                                         putchar ('\n');
  216.                                 continue;
  217.                         }
  218.  
  219.                         if (flag)
  220.                                 printf ("%s:\n", *av);
  221.                         printdir (lok);
  222.                         if (ac > 1)
  223.                                 putchar ('\n');
  224.                         UnLock (lok);  lok = NULL;
  225.                 }
  226.         }
  227.  
  228.         closestuff ();
  229.         my_proc->pr_WindowPtr = w_save;
  230. }
  231.  
  232.  
  233. /*
  234.  * This function prints the directory in a nice, pretty columnar format.
  235.  */
  236. printdir (dirlock)
  237. BPTR dirlock;
  238. {
  239.         struct List             namelist;
  240.         register struct Node    *name, **namearray;
  241.         long                    args[2], start, track_no, parent_block;
  242.         register int            i, n, j;
  243.         int                     len = 0, ncols, nlines, nfiles = 0;
  244.         char                    fmt1[16], fmt2[16];
  245.         char                    *fn = (char *) (&buf[FILENAME]) + 1;
  246.         struct disk_block *pdb, *ndb, *db;
  247.  
  248.         for (i = 0; i < 80; ++i)
  249.           tracks[i] = NULL;
  250.  
  251.         lock = (struct FileLock *) (dirlock << 2);
  252.         args[0] = parent_block = lock -> fl_Key;        /*  Block number  */
  253.         args[1] = (long) buf >> 2;      /*  BPTR to buffer  */
  254.  
  255.         /*  Attempt to get raw directory block.  */
  256.         if (!dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2)) {
  257.                 if (packet -> sp_Pkt.dp_Res2 == ERROR_ACTION_NOT_KNOWN)
  258.                         printf ("Not a block device.\n");
  259.                 else
  260.                         printf ("Error %ld while getting dirblock.\n",
  261.                                 packet -> sp_Pkt.dp_Res2);
  262.                 return;
  263.         }
  264.  
  265.         /*  Copy DOS's hash table into our array.  */
  266.         for (i=0; i<TABSIZ; i++)
  267.                 hashtab[i] = buf[i+STARTTAB];
  268.  
  269.         NewList (&namelist);
  270.         while (1) {
  271.                 /*  Sort hash table.  */
  272.                 qsort (hashtab, TABSIZ, sizeof (long), longcmp);
  273.                 if (!hashtab[0])        /*  Empty hash table  */
  274.                         break;
  275.  
  276.                 /*
  277.                  * Retrieve disk blocks according to sorted hash table and
  278.                  * collect filenames.
  279.                  */
  280.                 for (i=0; hashtab[i] && i<TABSIZ; i++)
  281.                 {
  282.                   track_no = hashtab[i]/22;
  283.                   if (db = tracks[track_no])
  284.                   {
  285.                     /*********************************
  286.                       We have already hit this track
  287.                       so get the information from
  288.                       our list of other blocks.
  289.                       Doing this prevents seeking
  290.                       several times to the same track.
  291.  
  292.                       first find the block in the list
  293.                     **********************************/
  294.  
  295.                     while (db->number != hashtab[i])  db = db->db;
  296.                     if (!(name = AllocMem (sizeof (*name) +
  297.                                            db->name[0] + 1L,
  298.                                            MEMF_CLEAR)))
  299.                     {
  300.                       puts ("Node memory allocation failure.");
  301.                       goto bombout;
  302.                     }
  303.  
  304.                     name -> ln_Name = (char *) name + sizeof (*name);
  305.                     name -> ln_Type = (db->type == ST_DIR);
  306.                     j = db->name[0];
  307.                     name->ln_Name[j] = 0;
  308.                     while (j)
  309.                     {
  310.                       name->ln_Name[j-1] = db->name[j];
  311.                       --j;
  312.                     }
  313.  
  314.                     AddTail (&namelist, name);
  315.                     nfiles++;   /*  Number of files found  */
  316.                     hashtab[i] = db->chain;
  317.                   }
  318.                   else
  319.                   {
  320.                     /*********************************
  321.                       We have never visited this track
  322.                       before, so we read all the blocks
  323.                       from it and stash away all those
  324.                       that are directory blocks, by doing
  325.                       this we don't ever have to go back
  326.                       to this track.  We don't record the
  327.                       contents of the block that caused
  328.                       us to process this track, instead
  329.                       we add it to the final name list
  330.                       directly.
  331.                     *************************************/
  332.  
  333.                     pdb = (struct disk_block *) &tracks[track_no];
  334.                     start = track_no*22;
  335.                     for (j = 0; j < 22; ++j)
  336.                     {
  337.                       args[0] = start+j;
  338.  
  339.                       /**************************************
  340.                         Make sure we never try to read the
  341.                         0 or 1 blocks as these are never used
  342.                         and will cause a GURU!
  343.                       ***************************************/
  344.  
  345.                       if ((args[0] == 0L) || (args[0] == 1L)) continue;
  346.                       dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2);
  347.                       if ((start+j)  == hashtab[i])
  348.                       {
  349.                         if (!(name = AllocMem (sizeof (*name) + *(fn-1) + 1L,
  350.                                                MEMF_CLEAR)))
  351.                         {
  352.                           puts ("Node memory allocation failure.");
  353.                           goto bombout;
  354.                         }
  355.  
  356.                         name -> ln_Name = (char *) name + sizeof (*name);
  357.                         name -> ln_Type = (buf[SECONDARY] == ST_DIR);
  358.                         fn[*(fn-1)] = '\0';     /*  Force null-termination  */
  359.                         strcpy (name -> ln_Name, fn);
  360.  
  361.                         AddTail (&namelist, name);
  362.                         nfiles++;       /*  Number of files found  */
  363.                         hashtab[i] = buf[HASHCHAIN];
  364.                       }
  365.                       else
  366.                           /**********************************
  367.                             Note: if blocks are not ST_SHORT
  368.                             then they do not contain user
  369.                             directories or file names.  Also
  370.                             to be a member of the directory
  371.                             we are scanning they must have
  372.                             the same parent block.
  373.                           ***********************************/
  374.                       {
  375.                         if ((buf[0] == ST_SHORT) &&
  376.                             (parent_block == buf[PARENT]))
  377.                         {
  378.                           /*********************************
  379.                             This block contains information
  380.                             which might be of future use so
  381.                             record it.
  382.                           **********************************/
  383.                           if (ndb = (struct disk_block *)
  384.                               AllocMem((long) sizeof(struct disk_block), 0L))
  385.                           {
  386.                             pdb->db = ndb;
  387.                             ndb->db = NULL;
  388.                             ndb->type = buf[SECONDARY];
  389.                             movmem(&buf[BLOCKSIZE-20], &ndb->name, 64);
  390.                             ndb->chain = buf[HASHCHAIN];
  391.                             ndb->number = start+j;
  392.                             pdb = ndb;
  393.                           }
  394.                           else
  395.                             goto bombout;
  396.                         }
  397.                       }
  398.                     }  /* end for 22 blocks */
  399.                   }   /* end if new or old track */
  400.                 }    /* end scan the hash table */
  401.         }
  402.         if (!nfiles)    /*  No files  */
  403.                 return;
  404.  
  405.         /*  Create array that qsort can deal with.  */
  406.         if (!(namearray = AllocMem
  407.                            ((long) nfiles * sizeof (char *), MEMF_CLEAR))) {
  408.                 puts ("Name array allocation failure.");
  409.                 goto bombout;
  410.         }
  411.  
  412.         /*  Load up the array.  */
  413.         for (name = namelist.lh_Head, i=0;
  414.              name -> ln_Succ;
  415.              name = name -> ln_Succ, i++)
  416.                 namearray[i] = name;
  417.  
  418.         /*  Alphabetize filenames.  */
  419.         qsort (namearray, nfiles, sizeof (struct Node *), namecmp);
  420.  
  421.         /*  Find longest string so we can format intelligently.  */
  422.         for (i=0; i<nfiles; i++)
  423.                 if ((n = strlen (namearray[i] -> ln_Name)) > len)
  424.                         len = n;
  425.         len += 2;       /*  Inter-name spacing  */
  426.  
  427.         /*  Print them suckers out  */
  428.         ncols = 77 / len;               /*  Assume CON: is 77 columns  */
  429.         nlines = nfiles/ncols + (nfiles%ncols != 0);
  430.         sprintf (fmt1, "%%-%ds", len);          /*  Normal format string  */
  431.         sprintf (fmt2, "\033[33m%%-%ds\033[m", len);    /* For directories */
  432.         for (i=0; i<nlines; i++) {
  433.                 for (n=i; n<nfiles; n+=nlines)
  434.                         printf (namearray[n] -> ln_Type ? fmt2 : fmt1,
  435.                                 namearray[n] -> ln_Name);
  436.                 putchar ('\n');
  437.         }
  438.  
  439.         /*  Phew!  Now free all the stuff we allocated.  */
  440. bombout:
  441.         freenamelist (&namelist);
  442.         if (namearray)
  443.                 FreeMem (namearray, (long) nfiles * sizeof (struct Node *));
  444.  
  445.   /*****************************
  446.     free up any recorded disk
  447.     blocks from the track array
  448.   ******************************/
  449.  
  450.   for (i = 0; i < 80; ++i)
  451.   {
  452.     if (tracks[i])
  453.     {
  454.       db = tracks[i];
  455.       while( db = free_disk_block(db) ) ;
  456.     }
  457.   }
  458. }
  459.  
  460. freenamelist (list)
  461. struct List *list;
  462. {
  463.         register struct Node *now;
  464.  
  465.         while (now = RemTail (list))
  466.                 FreeMem (now, sizeof (*now) + strlen (now -> ln_Name) + 1L);
  467. }
  468.  
  469.  
  470. /*
  471.  * This function assumes the existence of a properly initialized
  472.  * standardpacket structure called "packet" and a reply port called
  473.  * "dosreply".  A more general function would not do this.
  474.  *
  475.  * This function is synchronous i.e. it doesn't return until the specified
  476.  * action has been performed.
  477.  */
  478. long
  479. dopacket (proc, action, args, nargs)
  480. struct MsgPort *proc;
  481. long action;
  482. register long *args;
  483. register int nargs;
  484. {
  485.         register long *argp = &packet -> sp_Pkt.dp_Arg1;
  486.  
  487.         for (; nargs>0; nargs--)
  488.                 *argp++ = *args++;
  489.  
  490.         /*
  491.          * AmigaDOS scribbles over the reply port, so we have to initialize
  492.          * it every time we send a packet.
  493.          */
  494.         packet -> sp_Pkt.dp_Port = dosreply;
  495.         packet -> sp_Pkt.dp_Type = action;
  496.  
  497.         PutMsg (proc, packet);
  498.         WaitPort (dosreply);
  499.         GetMsg (dosreply);
  500.  
  501.         return (packet -> sp_Pkt.dp_Res1);
  502. }
  503.  
  504.  
  505. /*
  506.  * These functions are called by qsort().  The sense of camparisons is
  507.  * reversed in longcmp to get a reverse sort (largest elements first).
  508.  */
  509. longcmp (foo, bar)
  510. long *foo, *bar;
  511. {
  512.         /*
  513.          * We have to do it this way because qsort() expects an int to be
  514.          * returned.  Subtracting longs directly might overflow a 16-bit int.
  515.          */
  516.         return ((*foo < *bar) - (*foo > *bar));
  517. }
  518.  
  519. namecmp (foo, bar)
  520. struct Node **foo, **bar;
  521. {
  522.         return (strcmp ((*foo) -> ln_Name, (*bar) -> ln_Name));
  523. }
  524.  
  525.  
  526. /*
  527.  * Resource allocation/deallocation routines.
  528.  */
  529. openstuff ()
  530. {
  531.         if (!(packet = AllocMem ((long) sizeof (*packet), MEMF_CLEAR)))
  532.                 die ("Can't allocate packet space.");
  533.  
  534.         if (!(dosreply = CreatePort (NULL, NULL)))
  535.                 die ("Dos reply port create failed.");
  536.         packet -> sp_Msg.mn_Node.ln_Name        = (char *) &packet -> sp_Pkt;
  537.         packet -> sp_Pkt.dp_Link                = &packet -> sp_Msg;
  538.  
  539.         if (!(fib = AllocMem ((long) sizeof (*fib), MEMF_CLEAR)))
  540.                 die ("Can't allocate FileInfoBlock.");
  541.  
  542.         /*
  543.          * Note:  This allocation may not work with DMA hard disks.
  544.          */
  545.         if (!(buf = AllocMem (BLOCKSIZE * 4L, MEMF_CHIP | MEMF_PUBLIC)))
  546.                 die ("Couldn't allocate sector buffer.");
  547. }
  548.  
  549. closestuff ()
  550. {
  551.         if (lok)                UnLock (lok);
  552.         if (buf)                FreeMem (buf, BLOCKSIZE * 4L);
  553.         if (fib)                FreeMem (fib, (long) sizeof (*fib));
  554.         if (dosreply)           DeletePort (dosreply);
  555.         if (packet)             FreeMem (packet, (long) sizeof (*packet));
  556. }
  557.  
  558. die (str)
  559. char *str;
  560. {
  561.         puts (str);
  562.         closestuff ();
  563.         exit (1);
  564. }
  565.